package 单周赛.history;

import util.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 *
 */
public class 第319场单周赛 {

    public static void main(String[] args) {

        System.out.println(convertTemperature(122.11));

        System.out.println(subarrayLCM(new int[]{3, 6, 2, 7, 1}, 6));

        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(4);

        root.left = node2;
        root.right = node3;
        node2.left = node4;
        System.out.println(new 第319场单周赛().minimumOperations(root));

    }

    public static double[] convertTemperature(double celsius) {
        double[] ans = new double[2];

        ans[0] = celsius + 273.15D;
        ans[1] = celsius * 1.8D + 32;

        return ans;
    }

    /**
     * a 和 b 的最小公倍数 = a * b / a 和 b 的最大公约数
     *
     * @param nums
     * @param k
     * @return
     */
    public static int subarrayLCM(int[] nums, int k) {
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            int idx = i - 1;
            boolean flag = false;
            // 1 12 1 的情况，如果存在 12 1 的最小公倍数是 12，那么前面加上一个数 1 公倍数也是 12
            while (idx >= 0 && (flag && nums[idx] == 1 || nums[i] * nums[idx] / getMaxCommonDivisor(nums[i], nums[idx]) == k)) {
                idx--;
                flag = true;
            }
            count += (i - idx - 1);
            // 子数组为一个数为 = k 的情况
            if (nums[i] == k) {
                count++;
            }
        }

        return count;
    }

    // 最大公约数
    private static int getMaxCommonDivisor(int a, int b) {
        if (a == b) return a;
        a = Math.abs(a);
        b = Math.abs(b);
        int twoSquare = 1;
        while (a % 2 == 0 && b % 2 == 0) {
            a /= 2;
            b /= 2;
            twoSquare *= 2;
        }
        int min = Math.min(a, b), max = Math.max(a, b);
        while (min > 1) {
            int sub = max - min;
            if (sub == min) {
                break;
            }
            int tempMin = min;
            min = Math.min(tempMin, sub);
            max = Math.max(tempMin, sub);
        }
        return twoSquare * min;
    }

    /**
     * 广度搜索+选择排序
     *
     * @param root
     * @return
     */
    public int minimumOperations(TreeNode root) {
        int count = 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            int idx = 0;
            int[] sortArr = new int[size];

            while (size-- > 0) {
                TreeNode curNode = queue.pollFirst();
                sortArr[idx++] = curNode.val;

                if (curNode.left != null) {
                    queue.addLast(curNode.left);
                }
                if (curNode.right != null) {
                    queue.addLast(curNode.right);
                }
            }

            count += sort(sortArr);
        }

        return count;
    }

    private int sort(int[] sortArr) {
        int count = 0;


        int right = sortArr.length - 1;

        while (right > 0) {
            int maxNumIdx = 0;
            for (int i = 0; i <= right; i++) {
                if (sortArr[i] > sortArr[maxNumIdx]) {
                    maxNumIdx = i;
                }
            }

            if (sortArr[right] != sortArr[maxNumIdx]) {
                count++;
            }
            replace(sortArr, maxNumIdx, right);
            right--;
        }

        return count;
    }

    private void replace(int[] nums, int i, int j) {
        int numI = nums[i];
        nums[i] = nums[j];
        nums[j] = numI;
    }

}
